package contest.sweek203;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/24 18:02
 */
public class Solution4 {

    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] sum = new int[n];
        sum[0] = stoneValue[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + stoneValue[i];
        }

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j + i < n; j++) {
                int left = j;
                int right = j + i;

                int max = 0;
                for (int mid = left; mid < right; mid++) {
                    int sumleft = getsum(sum, left, mid);
                    int sumright = getsum(sum, mid + 1, right);

                    if (sumleft < sumright) {
                        max = Math.max(max, sumleft + dp[left][mid]);
                    } else if (sumleft > sumright) {
                        max = Math.max(max, sumright + dp[mid + 1][right]);
                    } else {
                        max = Math.max(max, sumleft + dp[left][mid]);
                        max = Math.max(max, sumright + dp[mid + 1][right]);
                    }
                }
                dp[left][right] = max;
            }
        }

        return dp[0][n - 1];
    }

    public int getsum(int[] sum, int left, int right) {
        if (left == 0) {
            return sum[right];
        }
        return sum[right] - sum[left - 1];
    }
}
